package com.skh.string;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @Author skh
 * @Date 2020/3/29 14:12
 * @Desc 特殊等价字符串组
 */
public class NumSpecialEquivGroups {
    /**
     * 你将得到一个字符串数组 A。
     *
     * 如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是特殊等价的。
     *
     * 一次移动包括选择两个索引 i 和 j，且 i ％ 2 == j ％ 2，交换 S[j] 和 S [i]。
     *
     * 现在规定，A 中的特殊等价字符串组是 A 的非空子集 S，这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。
     *
     * 返回 A 中特殊等价字符串组的数量。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：["a","b","c","a","c","c"]
     * 输出：3
     * 解释：3 组 ["a","a"]，["b"]，["c","c","c"]
     * 示例 2：
     *
     * 输入：["aa","bb","ab","ba"]
     * 输出：4
     * 解释：4 组 ["aa"]，["bb"]，["ab"]，["ba"]
     * 示例 3：
     *
     * 输入：["abc","acb","bac","bca","cab","cba"]
     * 输出：3
     * 解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]
     * 示例 4：
     *
     * 输入：["abcd","cdab","adcb","cbad"]
     * 输出：1
     * 解释：1 组 ["abcd","cdab","adcb","cbad"]
     */

    /**
     * 思路:搜集每个字符串中奇数位和偶数位的字符，按字典序排好序后使用Set来筛选
     */
    public int numSpecialEquivGroups(String[] A) {
        Set<String> set = new HashSet<>();
        for (String s : A) {
            String odd = "", even = "";
            for (int i = 0; i < s.length(); i++) {
                if (i % 2 == 0) {
                    even += s.charAt(i);
                } else {
                    odd += s.charAt(i);
                }
            }
            //排序
            char[] oddArray = odd.toCharArray();
            Arrays.sort(oddArray);
            char[] evenArray = even.toCharArray();
            Arrays.sort(evenArray);
            set.add(Arrays.toString(oddArray) + Arrays.toString(evenArray));
        }

        return set.size();
    }

    public static void main(String[] args) {
        NumSpecialEquivGroups numSpecialEquivGroups = new NumSpecialEquivGroups();
        String[] a = {"abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"};

        int i = numSpecialEquivGroups.numSpecialEquivGroups(a);
        System.out.println("i = " + i);
    }
}
